CSE 373: Data Structures and Algorithms

Winter 2000

Assignment 4 Chapter 5 Due February 4, 2000

 

Please include your name and student id # on what you turn in.

 

  1. Exercise 5.1 (a) and (b) (5.1 (a) and (b) in C++ book)

 

  1. Exercise 5.6 (5.8 in C++ book)

 

  1. Read Exercise 5.8 but answer only 5.9 (a), (b) and (c) (5.10 & 5.11 in C++ book)

 

  1. Examine the following C Macro definition

    #define CONTAINING_RECORD(address, type, field) \
        ((type *)( \
         (char *)(address) – \
         (unsigned int)(&((type *)0)->field)))

    This is actually a very useful macro for manipulating structures through embedded pointers.  It takes as parameters the address of a field within a structure, the name of the structure, and name of the field pointed at.  It returns a pointer to the start of the structure.  For example, consider the following typedefs and variable declarations

    typedef struct _LIST_ENTRY {
        struct _LIST_ENTRY *Flink;
        struct _LIST_ENTRY *Blink;
    } LIST_ENTRY *PLIST_ENTRY;

    typedef struct _MYSTRUCT {
        UNSIGNED int Age;
        UNSIGNED int Weight;
        LIST_ENTRY SortByAge;
        LIST_ENTRY SortByWeight;
    } MYSTRUCT *PMYSTRUCT;

    PLIST_ENTRY ByAge;
    PLIST_ENTRY ByWeight;

    If we have a pointer to the SortByWeight field in a mystruct record we can easily get a pointer to the actual containing record by doing

    PtrToMyStruct = CONTAINING_RECORD(PtrToSortByWeight, MYSTRUCT, SortByWeight);

    Now assume that the two lists ByAge and ByWeight above are already sorted and each is the head of a circular doubly linked list.  The code fragment to find a record of a specific weight is thus

    PLIST_ENTRY Link;
    PMYSTRUCT MyStruct;

    Link = ByWeight->Flink;
    while (Link != &ByWeight) {

        MyStruct = CONTAINING_RECORD(Link, MYSTRUCT, SortByWeight);

        if (MyStruct->Weight == WeightLookingFor) {

            //
            //  This is the weight we want
            //

            printf(“Found the weight\n”);

        } else if (MyStruct->Weight > WeightLookingFor) {

            //
            //  List does not contain this weight
            //

            break;
        }
    }

    Convince yourself how this actually works and then give a program fragment that takes a weight and age as input, allocates a new record and correctly inserts it on both lists.  Assume the weight and age will always be unique values, and don’t worry about error conditions.  I’m more interested in having you understand the basic locating and inserting algorithm needed to manipulate such a data structure.

  2. [not graded] How long did you spend on this assignment, and on a scale from 1 to 10 (1 being too easy, 5 being just about right, and 10 being too hard) please rate this assignment.